package demo.dynamicprogram;

public class DynamicUtil {
    public static void main(String[] args) {
        System.out.println(jump(new int[]{3, 2, 3, 1, 1, 4}));
    }

    /**
     * 跳跃问题
     *
     * @param arr
     * @return
     */
    public static int jump(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int jump = 0;
        int cur = 0;
        int next = 0;
        for (int i = 0; i < arr.length; i++) {
            if (cur < i) {
                jump++;
                cur = next;
            }

            next = Math.max(next, i + arr[i]);
        }
        return jump;
    }
}
